package com.dmall.graph.tree;

import com.dmall.graph.WeightedEdge;
import com.dmall.graph.WeightedGraph;
import com.dmall.graph.dfs.app.ConnectedComponent;

import java.util.ArrayList;
import java.util.List;

/**
 * Prim算法寻找最小生成树
 * 使用了切分定理
 * 最开始将0顶点和V - 1个顶点进行切分，
 * 每次切分完成后，将其中的最小横切边的顶点纳入到一边
 * 最后完成所有顶点的切分
 * @author xiao1.wang
 * @date 2022-08-05 09:42:27
 */
public class Prim1 {
    private WeightedGraph G;
    private List<WeightedEdge> mst;

    public Prim1(WeightedGraph G) {
        this.G = G;
        this.mst = new ArrayList<>(G.E());

        ConnectedComponent cc = new ConnectedComponent(G);
        if (cc.count() > 1) {
            return;
        }
        // Prim
        boolean[] visited = new boolean[G.V()];
        visited[0] = true;
        for (int i = 1; i < G.V(); i++) {
            WeightedEdge minEdge = new WeightedEdge(-1, -1, Integer.MAX_VALUE);
            for (int v = 0; v < G.V(); v++) {
                if (visited[v]) {
                    for (int w : G.adj(v)) {
                        if (!visited[w] && G.getWeight(v, w) < minEdge.getWeight()) {
                            minEdge = new WeightedEdge(v, w, G.getWeight(v, w));
                        }
                    }
                }
            }
            visited[minEdge.getV()] = true;
            visited[minEdge.getW()] = true;
            mst.add(minEdge);
        }
    }

    public List<WeightedEdge> result() {
        return mst;
    }

    public static void main(String[] args) {
        String filename = Prim1.class.getClassLoader().getResource("wg.txt").getPath();
        WeightedGraph g = new WeightedGraph(filename);
        Prim1 prim = new Prim1(g);
        System.out.println(prim.result());
    }
}
